import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.RandomAccessFile;


// -------------------------------------------------------------------------
/**
 *  This is a disk based hash table, relying on bucket hashing. Each bucket has
 *  32 slots and each slot holds two memory handles. One for the sequence ID
 *  memory handle and one for the sequence memory handle. Collsion resolution
 *  is solved by linear probing within a bucket. If no available space is found
 *  the sequence is not inserted.
 *
 *  @author Erik Rodriguez and Cory Chase
 *  @version May 9, 2013
 */
public final class HashTable {

	private final RandomAccessFile hashFile; //The file that holds the hash table.
	private final int tableSize; //The number of slots in the hash table.
	private final FileManager fMGR; //The file manager for the binary file

	private int[] currBucket; //The current bucket we are looking in within the hash table.
	private int currBucketNum; //The current bucket number.

	private final static int EMPTY = -1; //Indicate a slot is empty
	private final static int TOMBSTONE = -2; //Indicate a slot has been vacated

	private final static int NUM_SLOTS_PER_BUCKET = 32;
	private final static int INTEGERS_IN_SLOT = 4;
	private final static int INTEGER_SIZE = 4;
	private final static int BYTES_IN_SLOT = INTEGERS_IN_SLOT*INTEGER_SIZE;
	private final static int BYTES_IN_BUCKET = NUM_SLOTS_PER_BUCKET*BYTES_IN_SLOT;

	private final static int ID_LOCATION_OFFSET = 0;
	private final static int ID_LENGTH_OFFSET = 4;
	private final static int SEQUENCE_LOCATION_OFFSET = 8;
	private final static int SEQUENCE_LENGTH_OFFSET = 12;

	// ----------------------------------------------------------
	/**
	 * Create a new HashTable and initialize the file and current bucket.
	 * @param tableSize how many slots are in the table.
	 * @param hashFile the file the hash table is stored in.
	 * @param fMGR the file manager for the binary file
	 * @throws FileNotFoundException
	 */
	public HashTable(int tableSize, File hashFile, FileManager fMGR) throws FileNotFoundException{
		this.hashFile = new RandomAccessFile(hashFile,"rw");
		this.tableSize = tableSize;
		this.fMGR = fMGR;
		try {
			initializeTable();
		} catch (IOException e) {
			throw new FileNotFoundException("hashFile not intialized");
		}
		currBucketNum = 0;

	}

	/**
	 * Empty the hash file and seek to the beginning. Indicate all slots as empty.
	 */
	private void initializeTable() throws IOException{
		hashFile.seek(0);
		hashFile.setLength(tableSize);

		for(int i=0; i< this.tableSize * INTEGERS_IN_SLOT; i++){
			hashFile.writeInt(EMPTY);
		}
	}

	// ----------------------------------------------------------
	/**
	 * Read a new bucket from the hash file. Seek to the beginning of the bucket.
	 * @param slot
	 * @throws IOException
	 */
	public void setCurrBucket(int slot) throws IOException{
		int bucketNum = slot/NUM_SLOTS_PER_BUCKET;
		if(currBucket == null){
			hashFile.seek(0);
			int[] initBucket = new int[NUM_SLOTS_PER_BUCKET*INTEGERS_IN_SLOT];
			for(int i=0; i < NUM_SLOTS_PER_BUCKET*INTEGERS_IN_SLOT; i++){
				initBucket[i] = this.hashFile.readInt();
			}
			currBucket = initBucket;
		}
		else if(bucketNum != currBucketNum){
			hashFile.seek(bucketNum*BYTES_IN_BUCKET);

			int[] bucket = new int[NUM_SLOTS_PER_BUCKET*INTEGERS_IN_SLOT];

			for(int i=0; i < NUM_SLOTS_PER_BUCKET*INTEGERS_IN_SLOT; i++){
				bucket[i] = this.hashFile.readInt();
			}
			currBucket = bucket;
			currBucketNum = bucketNum;
		}
	}

	/**
	 * Jump to the next slot within a bucket.
	 * @return the slot number of the table
	 */
	private int nextSlot(int currSlot){
		if(currSlot%NUM_SLOTS_PER_BUCKET == NUM_SLOTS_PER_BUCKET - 1){
			return currSlot - NUM_SLOTS_PER_BUCKET + 1;
		}
		else
			return ++currSlot;
	}

	// ----------------------------------------------------------
	/**
	 * Insert two memory handles into a slot of the hash table. Hashes the sequence ID
	 * and starts at the beginning of the bucket and checks for an available
	 * slot to insert. If we loop back to the originial bucket there is no room to insert.
	 * @param sequenceID the sequence ID
	 * @param seqHandle
	 * @param idHandle
	 * @throws IOException
	 * @throws IllegalStateException
	 */
	public void insert(String sequenceID, MemBlock seqHandle, MemBlock idHandle) throws IOException, IllegalStateException{
		int originalSlot = (int) sfold(sequenceID, tableSize);
		int currSlot = originalSlot;
		boolean bucketFull = true;

		setCurrBucket(originalSlot);
		do {
			if (isSlotAvailable(currSlot)){
				writeToSlot(currSlot, seqHandle, idHandle);
				bucketFull = false;
				break;
			}
			else{
				if(sequenceIDAlreadyPresent(sequenceID, currSlot)){
					bucketFull = false;
					throw new IllegalStateException("Sequence Already Present");
				}
			}

			currSlot = nextSlot(currSlot);
		} while(currSlot != originalSlot);

		if(bucketFull){
			throw new IllegalStateException("Bucket being inserted to is full");
		}
	}

	// ----------------------------------------------------------
	/**
	 * Remove a sequence form the hash table. Hash the given sequence. First check
	 * if the hashed to slot has a sequence of the same length, if so, check if the
	 * IDs are equal, and if so, remove the sequence. Else, check the next slot.
	 * If we return to the orginial slot the sequence is not in the bucket, and cannot
	 * be removed.
	 * @param sequenceID
	 * @throws IOException
	 */
	public void remove(String sequenceID) throws IOException{

		int originalSlot = (int) sfold(sequenceID, tableSize);
		int currSlot = originalSlot;
		boolean removed = false;

		do {
			if (sequenceIDAlreadyPresent(sequenceID, currSlot)){
				MemBlock idHandle = new MemBlock(getIDLength(currSlot), getIDLocation(currSlot));
				MemBlock seqHandle = new MemBlock(getSequenceLength(currSlot), getSequenceLocation(currSlot));
				writeToSlot(currSlot, new MemBlock(TOMBSTONE, TOMBSTONE), new MemBlock(TOMBSTONE, TOMBSTONE));
				System.out.println("Sequence Removed " + sequenceID + ":");
				System.out.println(fMGR.removeSequence(idHandle, seqHandle, false));
				removed = true;
				break;
			}
			currSlot = nextSlot(currSlot);
		} while(currSlot != originalSlot);

		if(!removed)
			System.out.println(sequenceID + " is not found in the hash table!");
	}

	// ----------------------------------------------------------
	/**
	 * Search the hash table for a sequence ID. Hash the given ID and search the bucket
	 * for the sequence in the same way that remove searches.
	 * @param sequenceID
	 * @param output
	 * @return true if found, false if not
	 * @throws IOException
	 */
	public boolean search(String sequenceID, boolean output) throws IOException{
		int originalSlot = (int) sfold(sequenceID, tableSize);
		int currSlot = originalSlot;
		boolean found = false;

		setCurrBucket(originalSlot);
		do {
			if (sequenceIDAlreadyPresent(sequenceID, currSlot)){
				MemBlock seqHandle = new MemBlock(getSequenceLength(currSlot), getSequenceLocation(currSlot));
				if(output)
					System.out.println("Sequence found: " + fMGR.readHandle(seqHandle));
				found = true;
				break;
			}

			currSlot = nextSlot(currSlot);
		} while(currSlot != originalSlot);

		if(!found){
			if(output)
				System.out.println("SequenceID " + sequenceID + " not found.");
			return false;
		}
		else
			return true;

	}

	/**
	 * Checks whether the sequence ID in the hash table at a given slot is of the same
	 * length as the parameter, if so, check if they are equal, if so return true. Else return
	 * false.
	 * @return true if same, false if not
	 */
	private boolean sequenceIDAlreadyPresent(String sequenceID, int currSlot) throws IOException{
		if(getIDLength(currSlot) != sequenceID.length())
			return false;
		if(getID(getIDLocation(currSlot), getIDLength(currSlot)).equals(sequenceID))
			return true;
		else
			return false;
	}

	/**
	 * Writes the two memory handles to the hash table, and the current bucket.
	 * Sequence ID offset - Sequence ID length - Sequence offset - Sequence length
	 */
	private void writeToSlot(int writableSlot, MemBlock seqHandle, MemBlock idHandle) throws IOException{
		hashFile.seek(writableSlot*BYTES_IN_SLOT);
		hashFile.writeInt(idHandle.getOffset());
		currBucket[(writableSlot%NUM_SLOTS_PER_BUCKET)*INTEGERS_IN_SLOT] = idHandle.getOffset();
		hashFile.writeInt(idHandle.getLength());
		currBucket[(writableSlot%NUM_SLOTS_PER_BUCKET)*INTEGERS_IN_SLOT+1] = idHandle.getLength();
		hashFile.writeInt(seqHandle.getOffset());
		currBucket[(writableSlot%NUM_SLOTS_PER_BUCKET)*INTEGERS_IN_SLOT+2] = seqHandle.getOffset();
		hashFile.writeInt(seqHandle.getLength());
		currBucket[(writableSlot%NUM_SLOTS_PER_BUCKET)*INTEGERS_IN_SLOT+3] = seqHandle.getLength();
	}

	/**
	 * Returns whether the desired slot is available for insertion.
	 * @return true if available, and false if not
	 */
	private boolean isSlotAvailable(int slot){
		if (currBucket[(slot%NUM_SLOTS_PER_BUCKET)*INTEGERS_IN_SLOT] == EMPTY || currBucket[(slot%NUM_SLOTS_PER_BUCKET)*INTEGERS_IN_SLOT] == TOMBSTONE)
			return true;
		return false;
	}

	/**
	 * Gets ID length from the hash file.
	 */
	private int getIDLength(int currSlot) throws IOException{
		hashFile.seek(currSlot*BYTES_IN_SLOT + ID_LENGTH_OFFSET);
		return hashFile.readInt();
	}

	/**
	 * Gets the ID location from the hash file.
	 */
	private int getIDLocation(int currSlot) throws IOException{
		hashFile.seek(currSlot*BYTES_IN_SLOT + ID_LOCATION_OFFSET);
		return hashFile.readInt();
	}

	/**
	 * Gets the sequence length from the hash file.
	 */
	private int getSequenceLength(int currSlot) throws IOException{
		hashFile.seek(currSlot*BYTES_IN_SLOT + SEQUENCE_LENGTH_OFFSET);
		return hashFile.readInt();
	}

	/**
	 * Gets the sequence location from the hash file.
	 */
	private int getSequenceLocation(int currSlot) throws IOException{
		hashFile.seek(currSlot*BYTES_IN_SLOT + SEQUENCE_LOCATION_OFFSET);
		return hashFile.readInt();
	}

	/**
	 * Gets the ID from the file manager.
	 */
	private String getID(int idLocation, int idLength) throws IOException{
		return fMGR.readHandle(new MemBlock(idLength, idLocation));
	}

	/**
	 * Prints the currently filled slots in the hash table
	 * @throws IOException
	 *
	 */
	public void print() throws IOException{
		int curr = 0;
		for(int i=0; i<tableSize; i++){
			hashFile.seek(curr);
			int idLocation = hashFile.readInt();
			hashFile.seek(curr+=4);
			int idLength = hashFile.readInt();
			hashFile.seek(curr+=4);
			int seqLocation = hashFile.readInt(); //to advance the reader
			hashFile.seek(curr+=4);
			int seqLength = hashFile.readInt(); //to advance the reader
			hashFile.seek(curr+=4);
			if(idLocation == EMPTY || idLocation == TOMBSTONE){
				continue;
			}
			System.out.println(getID(idLocation, idLength) + ": hash slot[" + i + "]");

		}
	}

	// ----------------------------------------------------------
	/**
	 * The given hash function to hash sequence ID string.
	 * @param s the string
	 * @param M the table size
	 * @return the hash value
	 */
	long sfold(String s, int M) {
		  int intLength = s.length() / 4;
		  long sum = 0;
		  for (int j = 0; j < intLength; j++) {
		    char c[] = s.substring(j * 4, (j * 4) + 4).toCharArray();
		    long mult = 1;
		    for (int k = 0; k < c.length; k++) {
		      sum += c[k] * mult;
		      mult *= 256;
		    }
		  }

		  char c[] = s.substring(intLength * 4).toCharArray();
		  long mult = 1;
		  for (int k = 0; k < c.length; k++) {
		    sum += c[k] * mult;
		    mult *= 256;
		  }

		  sum = (sum * sum) >> 8;
		  return(Math.abs(sum) % M);
		}
}
